lib/Mi manual de algoritmos/version_maraton_interuniversitaria_2008-2/src/java/io_estandar.java

   1 import java.util.*;
   2 import java.io.*;
   3 import java.math.*;
   4
   5 class Main {
   6     public static void main(String[] args) throws IOException {
   7         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
   8         String line = reader.readLine();
   9         StringTokenizer tokenizer = new StringTokenizer(line);
  10         int N = Integer.valueOf(tokenizer.nextToken());
  11         while (N-- > 0){
  12             String a, b;
  13             a = reader.readLine();
  14             b = reader.readLine();
  15
  16             int A = a.length(), B = b.length();
  17             if (B > A){
  18                 System.out.println("0");
  19             }else{
  20                 BigInteger dp[][] = new BigInteger[2][A];
  21                 /*
  22 dp[i][j] = cantidad de maneras diferentes
  23 en que puedo distribuir las primeras i
  24 letras de la subsecuencia (b) terminando
  25 en la letra j de la secuencia original (a)
  26 */
  27
  28                 if (a.charAt(0) == b.charAt(0)){
  29                     dp[0][0] = BigInteger.ONE;
  30                 }else{
  31                     dp[0][0] = BigInteger.ZERO;
  32                 }
  33                 for (int j=1; j<A; ++j){
  34                     dp[0][j] = dp[0][j-1];
  35                     if (a.charAt(j) == b.charAt(0)){
  36                         dp[0][j] = dp[0][j].add(BigInteger.ONE);
  37                     }
  38                 }
  39
  40                 for (int i=1; i<B; ++i){
  41                     dp[i%2][0] = BigInteger.ZERO;
  42                     for (int j=1; j<A; ++j){
  43                         dp[i%2][j] = dp[i%2][j-1];
  44                         if (a.charAt(j) == b.charAt(i)){
  45                             dp[i%2][j] = dp[i%2][j].add(dp[(i+1)%2][j-1]);
  46                         }
  47                     }
  48                 }
  49                 System.out.println(dp[(B-1)%2][A-1].toString());
  50             }
  51         }
  52     }
  53 }